package KharkovITCourses.proc.loop.insertion_sort_optimized;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: root
 * Date: 1/3/13
 * Time: 9:59 AM
 * To change this template use File | Settings | File Templates.
 */
public class InsertionSort {
    public static void sort(int[] arr) {

        for (int border = 1; border < arr.length; border++) {
            int newElement = arr[border];
            int location = Arrays.binarySearch(arr, 0, border, arr[border]);
            if (location < 0)
                location = Math.abs(location) - 1;
            if (location != border) {
                System.arraycopy(arr, location, arr, location + 1, border - location);
                arr[location] = newElement;
            }
        }
    }
}
